// https://www.lintcode.com/problem/longest-common-substring/

public class Solution {
    /**
     * @param A: A string
     * @param B: A string
     * @return: the length of the longest common substring.
     */
    public int longestCommonSubstring(String A, String B) {
        // write your code here
        // 如果A[i]等于B[j]，那么子串的长度等于c[i - 1][j - 1] ＋ 1。
        int ret = 0;
        int[][] cache = new int[A.length() + 1][B.length() + 1];
        for (int i = 0; i < A.length(); ++i) {
            Arrays.fill(cache[i], 0);
        }
        for (int i = 1; i <= A.length(); ++i) {
            for (int j = 1; j <= B.length(); ++j) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    cache[i][j] = cache[i - 1][j - 1] + 1;
                } else {
                    cache[i][j] = 0;
                }
                ret = Math.max(ret, cache[i][j]);
            }
        }
        return ret;
    }
}